package com.z.test;

import java.util.Arrays;

public class MinHeapSort {

    // 最小堆排序
    public static void adjustMinHeap(int[] a, int pos, int len) {

        int temp;

        int child;

        for (temp = a[pos]; 2 * pos + 1 <= len; pos = child) {
            child = 2 * pos + 1;
            System.out.println("temp:" + temp +
                    ", pos:" + pos +
                    ", 2 * pos + 1:" + (2 * pos + 1) +
                    ", child:" + child +
                    " ," + Arrays.toString(a));

            if (child < len && a[child] > a[child + 1])

                child++;

            if (a[child] < temp)

                a[pos] = a[child];

            else

                break;

        }

        a[pos] = temp;

    }

    public static void minHeapSort(int[] array) {

        int i;

        int len = array.length;

        for (i = len / 2 - 1; i >= 0; i--) {
            System.out.println("i:" + i + " " + Arrays.toString(array));

            adjustMinHeap(array, i, len - 1);
            System.out.println("排序后:" + i + " " + Arrays.toString(array));
        }

        for (i = len - 1; i >= 0; i--) {
            System.out.println("i:" + i + " " + Arrays.toString(array));
            int tmp = array[0];

            array[0] = array[i];

            array[i] = tmp;

            adjustMinHeap(array, 0, i - 1);

        }

    }

    public static void main(String[] args) {

        int[] array = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };

        minHeapSort(array);

        System.out.println(Arrays.toString(array));

    }

}